{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Combination Sum III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: combinationSum3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #组合总和 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>找出所有相加之和为&nbsp;<code>n</code><em> </em>的&nbsp;<code>k</code><strong>&nbsp;</strong>个数的组合，且满足下列条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>只使用数字1到9</li>\n",
    "\t<li>每个数字&nbsp;<strong>最多使用一次</strong>&nbsp;</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <em>所有可能的有效组合的列表</em> 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <em><strong>k</strong></em> = 3, <em><strong>n</strong></em> = 7\n",
    "<strong>输出:</strong> [[1,2,4]]\n",
    "<strong>解释:</strong>\n",
    "1 + 2 + 4 = 7\n",
    "没有其他符合的组合了。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <em><strong>k</strong></em> = 3, <em><strong>n</strong></em> = 9\n",
    "<strong>输出:</strong> [[1,2,6], [1,3,5], [2,3,4]]\n",
    "<strong>解释:\n",
    "</strong>1 + 2 + 6 = 9\n",
    "1 + 3 + 5 = 9\n",
    "2 + 3 + 4 = 9\n",
    "没有其他符合的组合了。</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> k = 4, n = 1\n",
    "<strong>输出:</strong> []\n",
    "<strong>解释:</strong> 不存在有效的组合。\n",
    "在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 &gt; 1，没有有效的组合。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= k &lt;= 9</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 60</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [combination-sum-iii](https://leetcode.cn/problems/combination-sum-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [combination-sum-iii](https://leetcode.cn/problems/combination-sum-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n7', '3\\n9', '4\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        results = []\n",
    "        def backtrack(remain, comb, next_start):\n",
    "            if remain == 0 and len(comb) == k:\n",
    "                results.append(list(comb))\n",
    "                return\n",
    "            elif remain < 0 or len(comb) == k:\n",
    "                return\n",
    "            for i in range(next_start, 9):\n",
    "                comb.append(i + 1)\n",
    "                backtrack(remain-i-1, comb, i + 1)\n",
    "                comb.pop()\n",
    "        backtrack(n, [], 0)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        \n",
    "        def dfs(combination, target, pose):\n",
    "            if target == 0 or len(combination) == k:\n",
    "                if target == 0 and len(combination) == k:\n",
    "                    ans.append(combination)\n",
    "                else:\n",
    "                    return\n",
    "            \n",
    "            for i in range(pose, 10):\n",
    "                if i > target:\n",
    "                    break\n",
    "                dfs(combination+[i], target-i, i+1)\n",
    "        dfs([], n, 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def bt(res, cur, s, k, n):\n",
    "            if len(cur) > k:\n",
    "                return\n",
    "            elif len(cur) == k:\n",
    "                if s == n:\n",
    "                    res.append(cur[:])\n",
    "            else:\n",
    "                a = 1\n",
    "                if cur:\n",
    "                    a = cur[-1] + 1\n",
    "                while a < 10:\n",
    "                    cur.append(a)\n",
    "                    bt(res, cur, s + a, k, n)\n",
    "                    cur.pop()\n",
    "                    a += 1\n",
    "        res = []\n",
    "        bt(res, [], 0, k, n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        a=[]\n",
    "        def add(start,count,sums,nums):\n",
    "            if count>k or sums>n:\n",
    "                return\n",
    "            if count==k and sums==n:\n",
    "                a.append(nums)\n",
    "            for i in range(start+1,10):\n",
    "                add(i,count+1,sums+i,nums+[i])\n",
    "        add(0,0,0,[])\n",
    "        return a\n",
    "        '''\n",
    "        a=[]\n",
    "        for i in range(1,8):\n",
    "            if not n-i>=18:\n",
    "                for j in range(i+1,8):\n",
    "                    if not n-i-j>=9:\n",
    "                        if n-i-j<=9 and n-i-j>j:\n",
    "                            a.append([i,j,n-i-j])\n",
    "                        else:\n",
    "                            break\n",
    "                    else:\n",
    "                        break\n",
    "            else:\n",
    "                break\n",
    "        return a\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def DFS(self, res, tmp, nums, k, n, w, su):\n",
    "        if su==n and k==len(tmp):\n",
    "            res.append(tmp.copy())\n",
    "            return\n",
    "        elif su>n or len(tmp)>k:\n",
    "            return\n",
    "        for i in range(w,len(nums)):\n",
    "            su+=nums[i]\n",
    "            tmp.append(nums[i])\n",
    "            self.DFS(res,tmp,nums,k,n,i+1,su)\n",
    "            del tmp[-1]\n",
    "            su-=nums[i]\n",
    "\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        res=[]\n",
    "        tmp=[]\n",
    "        su=0\n",
    "        nums=[1,2,3,4,5,6,7,8,9]\n",
    "        self.DFS(res,tmp,nums,k,n,0,su)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        rl = []\n",
    "        self.func(0,[],0,0,rl,k,n)\n",
    "        return rl\n",
    "    def func(self,start,num,su,count,rl,k,n):\n",
    "        if count > k or su > n:\n",
    "            return\n",
    "        if count == k and su == n:\n",
    "            rl.append(num)\n",
    "            return\n",
    "        elif (count == k and su < n) or (count < k and su == n):\n",
    "            return\n",
    "        for i in range(start+1,10):\n",
    "           # print(num)\n",
    "            self.func(i,num+[i],su+i,count+1,rl,k,n)\n",
    "        \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        self.result = []\n",
    "        self.path = [0 for i in range(10)]\n",
    "        self.lens = 0\n",
    "        self.dfs(1, k, n)\n",
    "        return self.result\n",
    "        \n",
    "    def dfs(self, idx, k, target):\n",
    "        if target == 0 and k == 0:\n",
    "            temp = []\n",
    "            for i in range(self.lens):\n",
    "                temp.append(self.path[i])\n",
    "            self.result.append(temp)\n",
    "            return\n",
    "            \n",
    "        elif target < 0  or idx >= 10:\n",
    "            return\n",
    "        \n",
    "        # use\n",
    "        self.path[self.lens] = idx\n",
    "        self.lens += 1\n",
    "        self.dfs(idx + 1, k - 1, target - idx)\n",
    "        self.lens -= 1\n",
    "        \n",
    "        # not use\n",
    "        self.dfs(idx + 1, k, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        data = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "        return self.combinationSum(k, n, data)\n",
    "\n",
    "    def combinationSum(self, k, n, data):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        if k == 1:\n",
    "            if n in data:\n",
    "                result.append([n])\n",
    "        else:\n",
    "            for i, j in enumerate(data):\n",
    "                temp = self.combinationSum(k - 1, n - j, data[i + 1:])\n",
    "                for t in temp:\n",
    "                    result.append([j] + t)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        nums=[1,2,3,4,5,6,7,8,9]\n",
    "        ans=[]\n",
    "        def helper(n,pre,last):\n",
    "            p=sum(pre)\n",
    "            if p==n and len(pre)==k:\n",
    "                ans.append(pre)\n",
    "                return\n",
    "            if p>n:\n",
    "                return \n",
    "            for i in range(last+1,10):\n",
    "                helper(n,pre+[i],i)\n",
    "        helper(n,[],0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        if k<=0 or k>9 or n<=0 or n>45:\n",
    "            return []\n",
    "        res = []\n",
    "\n",
    "        def backTrack(m, cnt, total, tmp):\n",
    "            if cnt>k:\n",
    "                return\n",
    "            if cnt==k and total == n:\n",
    "                res.append(tmp)\n",
    "                return\n",
    "            for i in range(m, 10):\n",
    "                backTrack(i+1, cnt+1, total+i, tmp+[i])\n",
    "            \n",
    "        backTrack(1, 0, 0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        def backtrack(temp, K, summary, num):\n",
    "            if summary < 0:\n",
    "                return\n",
    "            if K == 0 and summary == 0:\n",
    "                res.append(temp)\n",
    "            if K == 0 and summary > 0:\n",
    "                return\n",
    "            for i in range(num, 0, -1):\n",
    "                backtrack(temp+[i], K-1, summary-i, i-1)\n",
    "        res = []\n",
    "        backtrack([], k, n, 9)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,pre_num,tmp_list,left_num,cur_num):\n",
    "        if pre_num == self.target and cur_num == self.target_num:\n",
    "            if sorted(list(tmp_list)) not in self.ans:\n",
    "                self.ans.append(sorted(list(tmp_list)))\n",
    "            return\n",
    "        if cur_num >= self.target_num:\n",
    "            return\n",
    "        if pre_num > self.target:\n",
    "            return\n",
    "        left_num_tmp = [i for i in left_num]\n",
    "        for num_tmp in left_num_tmp:\n",
    "            tmp_list.add(num_tmp)\n",
    "            left_num.remove(num_tmp)\n",
    "            self.dfs(pre_num+num_tmp,tmp_list,left_num,cur_num+1)\n",
    "            tmp_list.remove(num_tmp)\n",
    "            left_num.append(num_tmp)\n",
    "\n",
    "\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        self.target = n\n",
    "        self.target_num = k\n",
    "        self.ans = []\n",
    "        left_num = [1,2,3,4,5,6,7,8,9]\n",
    "        tmp_list = set()\n",
    "        self.dfs(0,tmp_list, left_num, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        val = [i+1 for i in range(9)]\n",
    "        res = []\n",
    "        def backtrack(tmp, total, idx, num):\n",
    "            if total == n and num == k:\n",
    "                res.append(tmp)\n",
    "                return \n",
    "            for i in range(idx, 9):\n",
    "                if total + val[i] > n: continue\n",
    "                backtrack(tmp+[val[i]], total+val[i], i+1, num+1)\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        candidates = list(range(1,10))\n",
    "        res = []\n",
    "        def backtrack(i, temp_sum, temp_list):\n",
    "            if temp_sum==n and len(temp_list)==k:\n",
    "                res.append(temp_list)\n",
    "                return\n",
    "            \n",
    "            if len(temp_list)==k:\n",
    "                return\n",
    "\n",
    "            for j in range(i, len(candidates)):\n",
    "                if len(temp_list)==k-1:\n",
    "                    if temp_sum+candidates[j]>n or temp_sum+candidates[-1]<n: # 稍微优化了一下\n",
    "                        break\n",
    "                backtrack(j+1, temp_sum+candidates[j], temp_list+[candidates[j]])\n",
    "        backtrack(0,0,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        self.combination(k, n, 1, [])\n",
    "        return self.res\n",
    "\n",
    "    def combination(self, k, target, start, res):\n",
    "        if len(res) == k and target == 0:\n",
    "            self.res.append(res)\n",
    "            return\n",
    "            \n",
    "        for i in range(start, 10):\n",
    "            self.combination(k, target-i, i+1, res+[i]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        self.combination(k, n, 1, [])\n",
    "        return self.res\n",
    "\n",
    "    def combination(self, k, target, start, res):\n",
    "        if len(res) == k and target == 0:\n",
    "            self.res.append(res)\n",
    "            return\n",
    "\n",
    "        if len(res) == k or target < 0:\n",
    "            return\n",
    "            \n",
    "        for i in range(start, 10):\n",
    "            self.combination(k, target-i, i+1, res+[i]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        @lru_cache(None)\n",
    "        def dfs(used, k, n, ci):\n",
    "            if k==0 and n==0:\n",
    "                return [[]]\n",
    "            elif k==0 or n==0:\n",
    "                return []\n",
    "            res = []\n",
    "            for i in range(ci, 10):\n",
    "                if 1<<i&used==0 and i<=n:\n",
    "                    ret = dfs(used|1<<i, k-1, n-i, i+1)\n",
    "                    for r in ret:\n",
    "                        res.append([i]+r)\n",
    "            return res\n",
    "        return dfs(0,k,n,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        @lru_cache(None)\n",
    "        def dfs(used, k, n, ci):\n",
    "            if k==0 and n==0:\n",
    "                return [[]]\n",
    "            elif k==0 or n==0:\n",
    "                return []\n",
    "            res = []\n",
    "            for i in range(ci, 10):\n",
    "                if 1<<i&used==0 and i<=n:\n",
    "                    ret = dfs(used|1<<i, k-1, n-i, i+1)\n",
    "                    for r in ret:\n",
    "                        res.append([i]+r)\n",
    "            return res\n",
    "        return dfs(0,k,n,1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "\n",
    "        def backtrack(n, k, sum_, startIndex):\n",
    "            if sum_ > n: return\n",
    "            if len(path) == k:\n",
    "                if sum_ == n:\n",
    "                    res.append(path[:])\n",
    "                return\n",
    "                \n",
    "            \n",
    "            for i in range(startIndex, 10):\n",
    "                path.append(i)\n",
    "                sum_ += i\n",
    "                backtrack(n, k, sum_, i + 1)\n",
    "                sum_ -= i\n",
    "                path.pop()\n",
    "        \n",
    "        backtrack(n, k, 0, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        def dfs(index,j,target):\n",
    "            if target==0 and index==k:\n",
    "                res.append(path.copy())\n",
    "            if target<0 or index>k:\n",
    "                return\n",
    "            for i in range(j,10):\n",
    "                path.append(i)\n",
    "                dfs(index+1,i+1,target-i)\n",
    "                path.pop()\n",
    "        res=[]\n",
    "        path=[]\n",
    "        dfs(0,1,n)\n",
    "        return res\n",
    "\n",
    "       \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        res=[]\n",
    "        def dfs(k,n,nums,i):\n",
    "            if k==0 and n==0:\n",
    "                res.append(nums[:])\n",
    "                return\n",
    "            if k<=0 or n<=0 or i>9:return\n",
    "            nums.append(i)\n",
    "            dfs(k-1,n-i,nums,i+1)\n",
    "            nums.pop()\n",
    "            dfs(k,n,nums,i+1)\n",
    "        \n",
    "        dfs(k,n,[],1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def __init__(self):\n",
    "        self.sum = 0\n",
    "        self.result = []\n",
    "        self.path = []\n",
    "    def combinationSum3(self, k,n):\n",
    "        def backtracking(k,n,startidx):\n",
    "            if len(self.path) == k:\n",
    "                if self.sum == n:\n",
    "                # 所以在这里k就是树的深度，什么时候遍历到叶子节点，\n",
    "                # 也就是什么时候，选完了k个数，那就什么时候终止即可。\n",
    "                    self.result.append(self.path[:])\n",
    "                # 这里不能只是appendpath，而是应该append（path[:]）\n",
    "                # 在这里的话，一维数组path存放符合条件的结果\n",
    "                # 二维数组result存放最终的结果集\n",
    "                    return\n",
    "                else:\n",
    "                    return\n",
    "\n",
    "                # 这句代码\n",
    "\n",
    "            # for i in range(startidx,n + 1):\n",
    "            for i in range(startidx, 9 - (k - len(self.path)) + 2):\n",
    "                self.sum += i\n",
    "                # 也就是说明取不到 n - (k - len(path)) + 2 这个值\n",
    "                # 如果是剪枝操作的话，应该就是上面这层for循环的写法\n",
    "                # for循环用来遍历集合中的每一个元素\n",
    "                self.path.append(i)\n",
    "                # 在这里有append，下面就有pop，在回溯的代码模板中，for循环中的 处理过程和 回溯操作是一一对应的\n",
    "                backtracking(k,n,i + 1)\n",
    "                self.sum -= i\n",
    "                # 这就说明，下一层搜索要从i的后面，也就是i+1开始\n",
    "                self.path.pop()\n",
    "\n",
    "        backtracking(k,n,1)\n",
    "        return self.result\n",
    "\n",
    "            # last_startidx = n - (k - len(path)) + 1\n",
    "# n = 4\n",
    "# k = 2\n",
    "# print(Solution().combine(n,k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        path, res = [], []\n",
    "        def backstracking(startidx, endidx):\n",
    "            if len(path) == k and sum(path) == n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            elif len(path) >= k:\n",
    "                return\n",
    "            print(len(path), startidx, endidx + 1 - (k - len(path)))\n",
    "            for i in range(startidx, endidx + 1 - (k - len(path))):\n",
    "                path.append(i)\n",
    "                backstracking(i + 1, 10)\n",
    "                path.pop()\n",
    "        backstracking(1, 10)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = []\n",
    "        self.path = []\n",
    "\n",
    "    def backtracking(self, startIndex, k, n, sums):\n",
    "        if sums > n:\n",
    "            return\n",
    "        if len(self.path) == k - 1:\n",
    "            if startIndex <= n - sum(self.path) < 10:\n",
    "                self.ans.append(self.path[:] + [n - sum(self.path)])\n",
    "            return\n",
    "        for i in range(startIndex, 11-(k-len(self.path))):\n",
    "            sums += i\n",
    "            self.path.append(i)\n",
    "            self.backtracking(i+1, k, n, sums)\n",
    "            self.path.pop()\n",
    "            sums -= i\n",
    "\n",
    "    def combinationSum3(self, k: int, n: int):\n",
    "        self.backtracking(1, k, n, 0)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "\n",
    "        def dfs(begin, size, k, target, path, res):\n",
    "            if len(path) == k:\n",
    "                if target == 0:\n",
    "                    res.append(path)\n",
    "                return\n",
    "            \n",
    "            for i in range(begin, size):\n",
    "                if target - i < 0:\n",
    "                    break\n",
    "                dfs(i + 1, size, k, target - i, path + [i], res)\n",
    "\n",
    "\n",
    "        path = []\n",
    "        res = []\n",
    "        dfs(1, 10, k, n, path, res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    k = 0\n",
    "    res = []\n",
    "    tmp = []\n",
    "    n = 0\n",
    "\n",
    "    def dfs(self, level):\n",
    "        if level == self.k: \n",
    "            if sum(self.tmp) == self.n:\n",
    "                self.res.append(self.tmp)\n",
    "            return\n",
    "        start = 1 if len(self.tmp) == 0 else self.tmp[-1]+1\n",
    "        for i in range(start, 10):\n",
    "            if i in self.tmp: continue\n",
    "            self.tmp.append(i)\n",
    "            self.dfs(level+1)\n",
    "            self.tmp = self.tmp[:-1]\n",
    "\n",
    "\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        self.k = k\n",
    "        self.n = n\n",
    "        self.res = []\n",
    "        self.tmp = []\n",
    "        self.dfs(0)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        def backtrace(cur_sum, n, k, path, result, start):\n",
    "            if cur_sum > n:\n",
    "                return\n",
    "            if cur_sum == n:\n",
    "                if len(path[:]) == k:\n",
    "                    result.append(path[:])\n",
    "                    return\n",
    "            \n",
    "            for i in range(start, 10):\n",
    "                cur_sum += i\n",
    "                path.append(i)\n",
    "                # 因为不能有重复数字，这里是得从i+1之后的\n",
    "                backtrace(cur_sum, n, k, path, result, i+1)\n",
    "                cur_sum -= i    \n",
    "                path.pop()\n",
    "        \n",
    "\n",
    "        path = []\n",
    "        result = []\n",
    "        backtrace(0, n, k, path, result, 1)\n",
    "        return result\n",
    "\n",
    "            \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
